#include<stdio.h>
#include<stdlib.h>
struct list
{
 int pre;
 int num;
 int next;
}chain[100001];
int main()
{
 int i,j=0,head,n,tnode,tnum,tnext,end,first;
 scanf("%d%d",&head,&n);
 for(i=0;i<n;i++)
 {
  scanf("%d%d%d",&tnode,&tnum,&tnext);
  chain[tnode].num=tnum;
  chain[tnode].next=tnext;
  chain[tnext].pre=tnode;
  if(tnext==-1)
   end=tnode;
 }
    first=head;
    while(first!=-1)
    {
        first=chain[first].next;
        j++;
    }
    n=j;
 while(n)
 {
  if(n==1)
  {
   head=-1; 
   printf("%05d %d %d\n",end,chain[end].num,head);
    break;
  }
  else
   printf("%05d %d %05d\n",end,chain[end].num,head);
   end=chain[end].pre;
  if(n==2)
  {
   end=-1;
   printf("%05d %d %d\n",head,chain[head].num,end);
    break;
  }
  else
   printf("%05d %d %05d\n",head,chain[head].num,end);
    head=chain[head].next;
    n-=2;
 }
 return 0;
}

//重排链表